nLab Kleisli category

Redirected from "Kleisli composition".
Kleisli category

Context

2-Category theory

Higher algebra

Kleisli category

Idea

Given a monad TT on some category 𝒞\mathcal{C}, then its Kleisli category is the full subcategory of the Eilenberg-Moore category of TT, hence the category of T-algebras, on those that are free T-algebras (free TT-modules).

Explicitly one may describe (Prop. below) the Kleisli category of TT (Def. ) to have as objects the objects of 𝒞\mathcal{C}, and a morphism XYX \to Y in the Kleisli category is a morphism in 𝒞\mathcal{C} of the form XT(Y)X \to T(Y) in 𝒞\mathcal{C}. The monad structure induces a natural composition of such “TT-shifted” morphisms.

The Kleisli category is also characterized by the following universal property:

Since every adjunction gives rise to a monad on the domain of its left adjoint, we might ask if every monad may be construed as arising from an adjunction. This is in fact true, and the initial such adjunction in the category of adjunctions for the given monad has the Kleisli category as the codomain of its left adjoint.

Definition

Let T=(T,μ,η)\mathbf{T} = (T,\mu,\eta) be a monad in Cat, where T:𝒞𝒞T \colon \mathcal{C} \longrightarrow \mathcal{C} is an endofunctor with

  • multiplication μ:TTT\mu \colon T T \to T,

  • unitη:Id CT\eta \colon Id_C \to T.

In terms of free algebras

Definition

A free T\mathbf{T}-algebra over a monad (or free T\mathbf{T}-module) is a T\mathbf{T}-algebra (module) of the form (T(M),μ M)(T(M),\mu_M), where the action is the component of multiplication transformation μ M:T(T(M))T(M)\mu_M : T(T(M))\to T(M).

Definition

The Kleisli category C TC_{\mathbf{T}} of the monad T\mathbf{T} is the full subcategory of the Eilenberg-Moore category C TC^{\mathbf{T}} on the free T\mathbf{T}-algebras (Def. ).

Remark

If U:C TCU:C^{\mathbf{T}}\to C is the forgetful functor and F:CC TF: C\to C^{\mathbf{T}} is the free algebra functor F:M(TM,μ M)F: M\mapsto (T M,\mu_M), then the Kleisli category is simply the full subcategory of C TC^{\mathbf{T}} containing those objects in the image of FF.

In terms of Kleisli morphisms

As another way of looking at this, we can keep the same objects as in CC but redefine the morphisms. This was the original Kleisli construction:

Definition

The Kleisli category C TC_{\mathbf{T}} of a monad TT on a category 𝒞\mathcal{C} has:

  1. as objects the objects of 𝒞\mathcal{C},

  2. as morphisms MNM \to N the morphisms of the form

    (1)MT(N) M \longrightarrow{\;\;} T(N)

    in 𝒞\mathcal{C}, called Kleisli morphisms;

and

  • composition of MfTNM \xrightarrow{f} T N with NgTPN \xrightarrow{ g } T P is given by the Kleisli composition rule

    (2)g Kleislifμ PT(g)f:MfT(N)T(g)T(T(P))μ PT(P); g \circ_{Kleisli} f \;\coloneqq\; \mu_P \circ T(g) \circ f \;\colon\; M \overset{f}{\longrightarrow} T (N) \overset{T (g)}{\longrightarrow} T \big(T (P)\big) \overset{\mu_P}{\longrightarrow} T (P) \,;
  • the identity morphisms on MM is the Kleisli morphism which is the T T -unit Mη MTMM \xrightarrow{ \eta_M } T M.

Proposition

(Kleisli equivalence)
The construction which sends a Kleisli morphism XfTYX \xrightarrow{f} T Y (1) to

T(X)T(f)T 2(Y)μ YT(Y) T(X) \overset{T(f)}{\longrightarrow} T^2(Y) \overset{\mu_Y}{\longrightarrow} T(Y)

constitutes a fully faithful functor

𝒞 T𝒞 T \mathcal{C}_{T} \xhookrightarrow{\phantom{--}} \mathcal{C}^{T}

from the TT-Kleisli category (Def. ) to the category of T T -algebras, hence constitutes an equivalence of categories onto its essential image (the free TT-algebras).

(eg. Borceux (1994), Prop. 4.1.6)

Proof

To see that the functor is full, hence that fμ YT(f)f \mapsto \mu_Y \circ T(f) is surjective, oberve that any homomorphism g:T(X)T(Y)g \colon T(X) \to T(Y) of algebras is the image of Xη XT(X)gT(Y)X \stackrel{\eta_X}{\to} T(X) \stackrel{g}{\to} T(Y), as shown by the following commuting diagram:

Here the triangle on the left is the unit law of the monad, while the commutativity of the square is the fact that GG is a homomorphism of algebras.

To see that the functor is faithful, hence that fμ YT(f)f \mapsto \mu_Y \circ T(f) is injective, notice that

(μ YT(f))η X=f, \big( \mu_Y \circ T(f) \big) \circ \eta_X \;=\; f \,,

by naturality of the unit η X\eta_X combined with its unit law:

whence

μ YT(f)=μ YT(g)μ YT(f)η X=μ YT(g)η Xf=g. \mu_Y \circ T(f) \,=\, \mu_Y \circ T(g) \;\;\;\;\;\; \Rightarrow \;\;\;\;\;\; \mu_Y \circ T(f) \circ \eta_X \,=\, \mu_Y \circ T(g) \circ \eta_X \;\;\;\;\;\; \Leftrightarrow \;\;\;\;\;\; f \,=\, g \,.

Remark

This Kleisli composition plays an important role in computer science; for this, see the article at monad (in computer science).

Two-sided Kleisli category

Proposition

If in addition to the given monad \mathcal{E} there is a comonad 𝒞\mathcal{C} on the same category C\mathbf{C}, equipped with a distributivity law (see there)

distr 𝒞,:𝒞((D))(𝒞(D)) distr^{\mathcal{C}, \mathcal{E}} \;\;\colon\;\; \mathcal{C} \big( \mathcal{E}(D) \big) \longrightarrow \mathcal{E} \big( \mathcal{C}(D) \big)

then there is a two-sided (“double”) Kleisli category whose objects are those of C\mathbf{C}, and whose morphisms D 1D 2D_1 \to D_2 are morphisms in C\mathbf{C} of the form

prog 12:𝒞(D 1)(D 2) prog_{12} \;\colon\; \mathcal{C}(D_1) \longrightarrow \mathcal{E}(D_2)

with two-sided Kelisli composition

prog 12>=>prog 23:𝒞(D 1)(D 3) prog_{12} \text{>=>} prog_{23} \;\; \colon \;\; \mathcal{C}(D_1) \longrightarrow \mathcal{E}(D_3)

given by the (co-)bind-operation on the factors connected by the distributivity transformation:

(Brookes & Van Stone 1993 Thm. 2)

Proposition

In the situation of Prop. , given in addition:

  1. \mathcal{E}' another monad on C\mathbf{C}

    • also equipped with distributivity distr 𝒞,:𝒞𝒞distr^{\mathcal{C}, \mathcal{E}'} \,\colon\, \mathcal{C}\circ \mathcal{E}' \to \mathcal{E}' \circ \mathcal{C} over the given comonad 𝒞\mathcal{C},
  2. a monad transformation trans :trans^{\mathcal{E} \to \mathcal{E}'} \,\colon\, \mathcal{E} \to \mathcal{E}'

    • which is compatible with the distributive laws in that that

then the usual compatibility of the one-sided-Kleisli category under monad transformations (see here) passes to the two-sided Kleisli category, in that

(3)(trans D 2 prog 12)>=>(trans D 3 prog 23)=trans D 3 (prog 12>=>prog 23). \big( trans^{ \mathcal{E} \to \mathcal{E}' }_{D_2} \circ prog_{12} \big) \;\; \text{>=>} \;\; \big( trans^{ \mathcal{E} \to \mathcal{E}' }_{D_3} \circ prog_{23} \big) \;\;\; = \;\;\; trans^{ \mathcal{E} \to \mathcal{E}' }_{D_3} \circ \big( prog_{12} \;\text{>=>}\; prog_{23} \big) \,.

Proof

Consider the following diagram:

Here all squares commute by assumption on the monad transformation and hence the entire diagram commutes. Now the total top and right composite is the right hand side of (3), while the total left and bottom composite is the left hand side of (3), thus proving their equality.

Properties

Adjunction

Each Kleisli category comes with an adjunction

In terms of Kleisli morphisms:

  • The functor L:𝒞𝒞 TL:\mathcal{C}\to\mathcal{C}_T is the identity on objects, and on morphisms it maps f:XYf:X\to Y to the Kleisli morphism defined by η Yf:XTY\eta_Y\circ f:X\to T Y, where η\eta is the unit of the monad.
  • The functor R:𝒞 T𝒞R:\mathcal{C}_T\to\mathcal{C} maps an object XX to the object TXT X, and a Kleisli morphism defined by k:XTYk:X\to T Y to its Kleisli extension μ YTk:TXTY\mu_Y\circ T k:T X\to T Y, where μ\mu is the multiplication of the monad.

In terms of free algebras:

  • The functor L:𝒞𝒞 TL:\mathcal{C}\to\mathcal{C}_T maps an object XX to the free algebra (TX,μ X)(T X,\mu_X), where μ\mu is the multiplication of the monad, and a morphism f:XYf:X\to Y to the morphism of algebras Tf:TXTYT f: T X\to T Y.
  • The functor R:𝒞 T𝒞R:\mathcal{C}_T\to\mathcal{C} is the forgetful functor mapping free algebras and morphisms of algebras to the underlying objects and morphisms of 𝒞\mathcal{C}.

Universal properties

In more general 2-categories the universal properties of Kleisli objects are dual to the universal properties of Eilenberg-Moore objects.

In particular, C TC_{\mathbf{T}} is initial in the category of adjunctions for T\mathbf{T} (whereas C TC^{\mathbf{T}} is terminal). For a proof, see Category Theory in Context Proposition 5.2.12.

Limits and colimits

Proposition

A limit in 𝒞\mathcal{C} is preserved by L:𝒞𝒞 TL:\mathcal{C}\to\mathcal{C}_T if and only if it is preserved by the monad T:𝒞𝒞T:\mathcal{C}\to\mathcal{C}.

Proof

Let DD be a diagram in 𝒞\mathcal{C}, and suppose its limit exists.

First, suppose that the limit of DD is preserved by LL. Then since R:𝒞 T𝒞R:\mathcal{C}_T\to\mathcal{C} is right adjoint, it preserves limits, and so the limit of DD is also preserved by T=RLT=R\circ L.

Conversely, denote by U:𝒞 T𝒞U:\mathcal{C}^T\to\mathcal{C} the forgetful functor from the Eilenberg-Moore category of TT, and denote by J:𝒞 T𝒞 TJ:\mathcal{C}_T\to\mathcal{C}^T the comparison functor. We have that R:𝒞 T𝒞R:\mathcal{C}_T\to\mathcal{C} factors as UJU\circ J, and so T=UJLT=U\circ J\circ L. Now suppose that the limit of DD is preserved by T=UJLT=U\circ J\circ L. Since UU is monadic and monadic functors create limits, the limit is also preserved by the functor JL:𝒞𝒞 TJ\circ L:\mathcal{C}\to\mathcal{C}^T. Now since JJ is a full inclusion, and full inclusions reflect limits, the limit is also preserved by the functor L:𝒞𝒞 TL:\mathcal{C}\to\mathcal{C}_T alone.

Examples

General

Example

In typed functional programming, the Kleisli category is used to model call-by-value? functions with side effects and computation. Dually, the co-Kleisli category of a comonad may be used to model call-by-name? programming , see there.

Generally, see at monad (in computer science) for more on this.

Specific

Example

(matrix multiplication as (co-)Kleisli composition)
See here.

References

The original articles:

Early accounts (together with the Eilenberg-Moore category):

The equivalence of categories between the Kleisli category over a given monad with the co-Kleisli category of an adjoint comonad (if it exists):

The terminology “Kleisli triple” for a monad presented as an “extension system” and relation to computation with effects (see at monads in computer science):

Textbook account making explicit the Kleisli equivalence:

Lecture notes:

Discussion of cases where the inclusion of the Kleisli category into the Eilenberg-Moore category is a reflective subcategory:

  • Marcelo Fiore, Matias Menni, Reflective Kleisli subcategories of the category of Eilenberg-Moore algebras for factorization monads, Theory and Applications of Categories, Vol. 15, CT2004, No. 2, pp 40-65. (TAC)

Discussion of combined “double” or “two-sided” Kleisli categories, combining the Kleisli category of a monad with the co-Kleisli category of a comonad that distributes over it:

and generalization to 2-monads:

Discussion in internal category theory:

  • Tomasz Brzeziński, Adrian Vazquez-Marquez, Internal Kleisli categories, Journal of Pure and Applied Algebra 215 9 (2011) 213-147 [arXiv:0911.4048]

Discussion in a context of categorical systems theory:

Discussion of Kleisli categories in type theory is in

Last revised on July 28, 2024 at 14:11:32. See the history of this page for a list of all contributions to it.